/**
 *      author: Y_Yao
 *      created: 2024-09-13 23:21:13
 **/

#include <bits/stdc++.h>

using namespace std;
const int N = 20;
int nums[N];
bool row[N], up[N], down[N];
int ret;
int n;

void dfs(int m)
{
    if (m == n - 1)
    {
        ret++;
        if (ret <= 3)
        {
            for (int i = 0; i < n; i++)
                cout << nums[i] << " ";
            cout << endl;
        }
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (row[i] || up[m + 1 + i] || down[m + 1 - i + n])
            continue;
        row[i] = up[m + 1 + i] = down[m + 1 - i + n] = true;
        nums[m + 1] = i + 1;
        dfs(m + 1);
        row[i] = up[m + 1 + i] = down[m + 1 - i + n] = false;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    dfs(-1);
    cout << ret << endl;
    return 0;
}